
package com.studiofortress.sf.util.collections;

import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;

/**
 * This is a single-linked linked list implementation which will cache it's
 * internal data structures. It is designed for cases where you are very often
 * adding and removing the same number of objects.
 *
 * The internal nodes must be explicitely cleared.
 * 
 * @author Joseph Lenton - JosephLenton@StudioFortress.com
 */
public class CachingLinkedList<V> implements List<V>, CallbackIterable<V>
{
    private Node<V> firstNode;
    private Node<V> lastNode;
    private int size;
    private int failNum;
    private final ObjectStack< Node<V> > cachedNodes;
    private final ObjectStack< ReusableIterator > cachedIterators;

    public CachingLinkedList()
    {
        firstNode = null;
        lastNode = null;
        size = 0;
        cachedNodes = new ObjectStack< Node<V> >();
        cachedIterators = new ObjectStack< ReusableIterator >(2);
    }
    
    /**
     * Iterates over all of the elements in this list and for each value runs
     * the given callback.
     * @param callback The callback to run each element in this list against, cannot be null.
     */
    @Override
    public void iterate(CallbackIterator<V> callback)
    {
        if ( callback == null ) {
            throw new IllegalArgumentException("The given iterator cannot be null.");
        }

        for ( Node<V> node = firstNode;
                node != null;
                node = node.next )
        {
            callback.iterate( node.val );
        }
    }

    @Override
    public void iteratePartial(CallbackPartialIterator<V> callback)
    {
        if ( callback == null ) {
            throw new IllegalArgumentException("The given iterator cannot be null.");
        }

        callback.startIteration();
        for ( Node<V> node = firstNode;
                node != null && callback.isIterating();
                node = node.next )
        {
            callback.iterate( node.val );
        }
    }

    /**
     * Increments the failure number.
     */
    private final void incrementFailNum()
    {
        failNum++;
    }

    /**
     * @return The failure number which is used to detect changes.
     */
    private final int getFailNum()
    {
        return failNum;
    }

    /**
     * @return The current number of elements in this list.
     */
    public int size()
    {
        return size;
    }

    /**
     * @return True if there are no elements in this list, otherwise false.
     */
    public boolean isEmpty()
    {
        return size() == 0;
    }

    /**
     * The contains check is that the value checked equals obj through obj's
     * equals method, or that both obj and an element equals null.
     * @param obj The object to find in this list.
     * @return True if obj.equals( element ) or if both obj and element are null.
     */
    public boolean contains(Object obj)
    {
        if (obj == null) {
            for (Node<V> node = firstNode; node != null; node = node.next) {
                if ( node.val == null ) {
                    return true;
                }
            }
        } else {
            for (Node<V> node = firstNode; node != null; node = node.next) {
                if ( obj.equals(node.val) ) {
                    return true;
                }
            }
        }
        
        return false;
    }

    public Iterator<V> iterator()
    {
        return newIterator();
    }

    /**
     * @return An array containing all the elements in this list.
     */
    public Object[] toArray()
    {
        final Object[] returnArr = new Object[ size() ];
        int i = 0;

        for (Node<V> node = firstNode; node != null; node = node.next) {
            returnArr[ i++ ] = node.next;
        }

        return returnArr;
    }

    /**
     * If the given array is big enough, then all the elements of this array are
     * placed into it to fill from index 0 to size (exclusive). Otherwise a new
     * array will be created and returned.
     * @param <T> The type of the elements when returned.
     * @param returnArray The array to store the elements into, or to define the type of array to create and return.
     * @return An array containing all the elements in this array of type T.
     */
    public <T> T[] toArray(T[] returnArray)
    {
        final int localSize = size();
        if (localSize < returnArray.length) {
            returnArray = (T[]) new Object[ localSize ];
        }
        
        int i = 0;
        for (Node<V> node = firstNode; node != null; node = node.next) {
            returnArray[ i++ ] = (T) node.next;
        }
        
        return returnArray;
    }

    /**
     * Adds the given value to the end of this list, it is the same as calling
     * add( val ).
     * @param val The value to add to this list.
     */
    public void addLast(final V val)
    {
        add( val );
    }

    /**
     * Adds the given val to the beginning of this list.
     * @param val The value to add.
     */
    public void addFirst(final V val)
    {
        final Node<V> newNode = newNode( val, null, firstNode );
        if (firstNode != null) {
            firstNode.previous = newNode;
        } else {
            lastNode = newNode;
        }
        
        incrementFailNum();
        firstNode = newNode;
        size++;
    }
    
    /**
     * Adds the given value to the end of this list.
     * @param val The value to add.
     * @return True if the element was added (should always be true).
     */
    public boolean add(V val)
    {
        final Node<V> newNode = newNode( val, lastNode, null );
        
        if (lastNode != null) {
            lastNode.next = newNode;
        } else {
            firstNode = newNode;
        }

        incrementFailNum();
        lastNode = newNode;
        size++;
        return true;
    }

    /**
     * @param index The index of the item to retrieve.
     * @return The item stored under the given index.
     */
    public V get(int index)
    {
        final int localSize = size();
        if (index < 0 || index >= localSize) {
            throw new ArrayIndexOutOfBoundsException( index );
        }

        int i = 0;
        if (index <= localSize/2) {
            for (Node<V> node = firstNode; node != null; node = node.next) {
                if (i++ == index) {
                    return node.val;
                }
            }
        } else {
            for (Node<V> node = lastNode; node != null; node = node.previous) {
                if (--i == index) {
                    return node.val;
                }
            }
        }

        throw new IllegalStateException("This point of code should never be reached.");
    }

    /**
     * @return The last element in this list, or throw an exception if this is empty.
     */
    public V element()
    {
        if ( lastNode == null ) {
            throw new NoSuchElementException("There are no elements to return.");
        }
        
        return lastNode.val;
    }

    /**
     * This is the same as calling getLast() or element(), except that if this
     * is empty then null will be returned.
     * @return The last element at the end of this list.
     */
    public V peek()
    {
        return (lastNode == null) ? null : lastNode.val;
    }

    public V peekLast()
    {
        return peek();
    }

    public V peekFirst()
    {
        return (firstNode == null) ? null : firstNode.val;
    }

    /**
     * This is the same as calling element. This will throw an exception if this
     * list is empty.
     * @return The last elements added to this list.
     */
    public V getLast()
    {
        return element();
    }

    /**
     * @return The first element in this list.
     */
    public V getFirst()
    {
        if (firstNode == null) {
            throw new NoSuchElementException("The list is empty.");
        }

        return firstNode.val;
    }

    /**
     * @return Removes the last element in this list, or throws an exception if this is empty.
     */
    public V remove()
    {
        if ( isEmpty() ) {
            throw new NoSuchElementException("Removing when the list is empty.");
        } else {
            final V val = lastNode.val;
            final Node<V> node = lastNode;

            lastNode = lastNode.previous;
            if (lastNode != null) {
                lastNode.next = null;
            }

            cacheNode( node );
            incrementFailNum();
            size--;

            return val;
        }
    }

    /**
     * This is the same as calling remove().
     * @return The last item in this list, which is removed.
     */
    public V removeLast()
    {
        return remove();
    }

    /**
     * @return The first element in this list, which has also been removed.
     * @throws NoSuchElementException If this list is empty.
     */
    public V removeFirst()
    {
        if ( isEmpty() ) {
            throw new NoSuchElementException("Removing when the list is empty.");
        } else {
            final V val = firstNode.val;
            final Node<V> node = firstNode;
            
            firstNode = firstNode.next;
            if (firstNode != null) {
                firstNode.previous = null;
            }

            cacheNode( node );
            incrementFailNum();
            size--;

            return val;
        }
    }

    /**
     * Removes the first instance found that matches the object given, from the
     * beginning of this list.
     * @param obj The object to remove.
     * @return True if the object was found and removed.
     */
    public boolean remove(Object obj)
    {
        if (obj == null) {
            for (Node<V> node = firstNode; node != null; node = node.next) {
                if ( node.val == null ) {
                    node.connectNextPrevious();

                    if (firstNode == node) {
                        firstNode = node.next;
                    }
                    if (lastNode == node) {
                        lastNode = node.previous;
                    }

                    cacheNode( node );
                    incrementFailNum();
                    size--;

                    return true;
                }
            }
        } else {
            for (Node<V> node = firstNode; node != null; node = node.next) {
                if ( obj.equals(node.val) ) {
                    node.connectNextPrevious();
                    
                    if (firstNode == node) {
                        firstNode = node.next;
                    }
                    if (lastNode == node) {
                        lastNode = node.previous;
                    }
                    
                    cacheNode( node );
                    incrementFailNum();
                    size--;

                    return true;
                }
            }
        }

        return false;
    }

    /**
     * @param collection A collection of items to search for.
     * @return True if all items in the given collection are contained in this list.
     */
    public boolean containsAll(Collection<?> collection)
    {
        if (collection == null) {
            throw new IllegalArgumentException("The given collection cannot be null.");
        }

        for (Object val : collection) {
            if ( !contains(val) ) {
                return false;
            }
        }

        return true && !isEmpty();
    }

    /**
     * Adds all of the items in the given collection to this list.
     * @param collection A collection of items to add, the collection itself cannot be null.
     * @return True if all items are added.
     */
    public boolean addAll(Collection<? extends V> collection)
    {
        if (collection == null) {
            throw new IllegalArgumentException("The given collection cannot be null.");
        }

        for (V val : collection) {
            add( val );
        }

        incrementFailNum();
        return true;
    }

    public boolean removeAll(Collection<?> collection)
    {
        if (collection == null) {
            throw new IllegalArgumentException("The given collection cannot be null.");
        }

        boolean removed = false;
        for (Object val : collection) {
            removed = removed || remove( (V) val );
        }

        incrementFailNum();
        return removed;
    }

    public boolean retainAll(Collection<?> collection)
    {
        final Object[] values = new Object[ collection.size() ];
        int numValues = 0;
        boolean altered = false;

        for (Object val : collection) {
            if ( remove((V) val) ) {
                values[numValues++] = val;
                altered = true;
            }
        }

        clear();

        for (int i = 0; i < numValues; i++) {
            add( (V) values[i] );
        }

        size = numValues;
        incrementFailNum();
        return altered;
    }

    /**
     * Cleares the linked list of all its elements.
     * The internal data structures used to store those elements used will be
     * cached for future use.
     */
    public void clear()
    {
        while (firstNode != null) {
            final Node<V> next = firstNode.next;
            cacheNode( firstNode );
            firstNode = next;
        }
        
        lastNode = null;
        incrementFailNum();
        size = 0;
    }

    /**
     * This does not cache the internal data structures and so just cleares its
     * self in the most performant way.
     */
    public void clearFast()
    {
        firstNode = null;
        lastNode = null;
        incrementFailNum();
        size = 0;
    }
    
    public void clearCache()
    {
        cachedNodes.clear();
        cachedIterators.clear();
    }
    
    private void cacheNode(Node<V> node)
    {
        node.val      = null;
        node.previous = null;
        node.next     = null;
        
        cachedNodes.push( node );
    }
    
    public int getCacheSize()
    {
        return cachedNodes.size();
    }
    
    private Node<V> newNode(V val, Node<V> previous, Node<V> next)
    {
        if (cachedNodes.isEmpty()) {
            return new Node(val, previous, next);
        } else {
            return cachedNodes.pop().initialize( val, previous, next );
        }
    }
    
    private void cacheIterator(ReusableIterator iterator)
    {
        iterator.node = null;
        iterator.lastNode = null;
        
        cachedIterators.push( iterator );
    }

    private ReusableIterator newIterator()
    {
        if (cachedIterators.isEmpty()) {
            return new ReusableIterator( getFailNum(), firstNode );
        } else {
            return cachedIterators.pop().initialize( getFailNum(), firstNode );
        }
    }

    /**
     * Adds all the values in the given collection to this list at the given
     * index. It's values will be placed in this list from index to
     * index+collection.size()
     * @param index The index to start adding the values from.
     * @param collection The collection of values to add to this list.
     * @return True.
     */
    public boolean addAll(int index, Collection<? extends V> collection)
    {
        for (V val : collection) {
            add( index++, val );
        }

        return true;
    }
    
    /**
     * Sets the value located at the given index to the new val.
     * @param index
     * @param newVal
     * @return The old value that was at the given index.
     */
    public V set(int index, V newVal)
    {
        final Node<V> node = getNode( index );

        final V oldVal = node.val;
        node.val = newVal;

        return oldVal;
    }

    /**
     * Adds the given element so it is stored at the given index.
     * @param index The index of where the element should be stored.
     * @param element The element to store.
     */
    public void add(int index, V element)
    {
        if (index == size()) {
            add( element );
        } else if (index == 0) {
            addFirst( element );
        } else {
            final Node<V> node = getNode( index );
            
            /* If the index is not the last index (it's not equal to size()-1)
             * and an exception has not been thrown, then there _must_ be a
             * node after the returned node. So no 'node == null' checks are
             * needed */
            
            final Node<V> newNode = newNode( element, node.previous, node );
            node.previous.next = newNode;
            node.previous = newNode;

            size++;
        }
    }
    
    /**
     * @param index The index of the node to retrieve.
     * @return The Node stored at the given index.
     */
    private Node<V> getNode(int index)
    {
        final int indexOfLastNode = size()-1;
        if (index < 0 || index > indexOfLastNode) {
            throw new ArrayIndexOutOfBoundsException(index);
        }

        Node<V> node;
        if (index < indexOfLastNode/2) {
            node = firstNode;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            node = lastNode;
            for (int i = indexOfLastNode; i > index; i--) {
                node = node.previous;
            }
        }

        return node;
    }

    public V remove(int index)
    {
        final Node<V> node = getNode( index );

        node.connectNextPrevious();
        final V oldVal = node.val;
        cacheNode( node );
        size--;

        return oldVal;
    }
    
    /**
     * @param obj The object to find in this list.
     * @return The index that the given object is stored at, or -1 if it is not found.
     */
    public int indexOf(Object obj)
    {
        int i = 0;
        for (Node<V> node = firstNode; node != null; node = node.next) {
            if (obj == node.val) {
                return i;
            } else {
                i++;
            }
        }

        return -1;
    }

    public int lastIndexOf(Object obj)
    {
        int i = size()-1; // -1 cos that's the last index
        for (Node<V> node = lastNode; node != null; node = node.previous) {
            if (obj == node.val) {
                return i;
            } else {
                i--;
            }
        }

        return -1;
    }

    /**
     * Unsupported and will throw an exception.
     * @return Nothing, this is unsupported.
     */
    public ListIterator<V> listIterator()
    {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    /**
     * Unsupported and will throw an exception.
     * @param index Ignored.
     * @return Nothing, this is unsupported.
     */
    public ListIterator<V> listIterator(int index)
    {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    /**
     * @param fromIndex The index to start adding elements from.
     * @param toIndex The index to add elements up too.
     * @return A sublist containing elements from the fromIndex to the toIndex, exclusively.
     */
    public List<V> subList(int fromIndex, int toIndex)
    {
        if (toIndex > size()) {
            throw new ArrayIndexOutOfBoundsException("toIndex is out of bounds, given: " + toIndex);
        } else if (toIndex < fromIndex) {
            throw new IllegalArgumentException("toIndex cannot be less then fromIndex; fromIndex: " + fromIndex + ", toIndex: " + toIndex);
        }

        final CachingLinkedList<V> subList = new CachingLinkedList<V>();
        Node<V> node = getNode(fromIndex);

        while (fromIndex < toIndex) {
            subList.add( node.val );
            node = node.next;
        }
        
        return subList;
    }
    
    private final class ReusableIterator implements Iterator<V>
    {
        private int failState;
        private Node<V> lastNode;
        private Node<V> node;

        public ReusableIterator(int failState, Node<V> node)
        {
            initialize( failState, node );
        }
        
        public ReusableIterator initialize(int failState, Node<V> node)
        {
            this.failState = failState;
            this.node = node;
            
            return this;
        }

        private final void checkFail()
        {
            if (failState != getFailNum()) {
                throw new ConcurrentModificationException("The list has been altered outside of this iterator.");
            }
        }

        public boolean hasNext()
        {
            checkFail();
            
            if (node == null) {
                cacheIterator( this );
                return false;
            } else {
                return true;
            }
        }

        public V next()
        {
            checkFail();

            lastNode = node;
            node = node.next;
            return lastNode.val;
        }

        public void remove()
        {
            checkFail();

            if (lastNode.previous != null) {
                lastNode.previous.next = node.next;
            }
            if (lastNode.next != null) {
                lastNode.next.previous = node.previous;
            }

            lastNode = null;
        }
    }
    
    private static final class Node<V>
    {
        private V val;
        private Node<V> previous;
        private Node<V> next;

        public Node(V val, Node<V> previous, Node<V> next)
        {
            initialize( val, previous, next );
        }

        public Node<V> initialize(V val, Node<V> previous, Node<V> next)
        {
            this.val      = val;
            this.previous = previous;
            this.next     = next;

            return this;
        }

        /**
         * Connects the node's before and after this node to each other,
         * removing this node from the link list chain. If either node is null
         * then that node will not be linked.
         */
        public final void connectNextPrevious()
        {
            if (next != null) {
                next.previous = previous;
            }
            if (previous != null) {
                previous.next = next;
            }
        }
    }
}
